package javatest.algorith;

import java.util.Stack;

/*
 * 单调栈
 */
public class MonotoneStack {
    public static void main(String[] args) {
        MonotoneStack ms = new MonotoneStack();
        int[] arr = {1,3,5,6,7};
        System.out.println(ms.maxProduct(arr));
        int[] arr2 = {2,3,5,6,7,2,6};
        System.out.println(ms.maxProduct(arr2));

        int[] arr3 = {1,4,2,3,5};
        int[][] result = ms.closeBigger(arr3);
        
        for (int[] is : result) {
            for (int is2 : is) {
                System.out.print(is2);    
                System.out.print(',');    
            }
            System.out.println();
        }
    }
    
    /*
     *  求非负数组的子数组中 和（sum） 与 最小值（min） 的乘积 最大的值
     */
    public int maxProduct(int[] arr) {
        int result = 0;

        for(int i=0; i<arr.length; i++){
            int curMax = maxProduct(arr, i);
            result = curMax > result ? curMax: result;
        }

        return result;
    }
    
    private int maxProduct(int[] arr, int index){
        int result = arr[index];
        int current = result;
        int preindex = index;
        int nextindex = index;
        while(true){
            preindex -= 1;
            nextindex += 1;
            boolean leftMax = preindex >= 0 && arr[preindex] >= current;
            if( leftMax ){
                result += arr[preindex];
            } 
            boolean rightMax = nextindex < arr.length && arr[nextindex] >= current;
            if ( rightMax ) {
                result += arr[nextindex];
            }
            if ( !leftMax && !rightMax ){
                break;
            }
        }
        return result * current;
    }
    
    public int maxProduct2(int[] arr) {
        int result = 0;
        Stack<Integer> s = new Stack<>();

        return result;
    }

    /*
     *  单调栈求数组中每一个数的 左右临近较大值
     *  [3,4,6,4,34,4,44,243]
     *  0 -> (null, 4)
     *  1 -> (null, 6)
     *  2 -> (null, 34)
     *  3 -> (6, 34)
     *  4 -> (null, 44)
     *  5 -> (34, 44)
     */
    public int[][] closeBigger(int[] arr) {
        int[][] result = new int[arr.length][2];
        Stack<Integer> s = new Stack<>();
        
        for(int i=0; i<arr.length; i++){
            if (s.isEmpty()){ 
                s.add(i);
            }else{
                while(!s.isEmpty()){
                    if(arr[s.peek()] < arr[i]) {
                        int curIndex = s.pop();
                        result[curIndex][1] = i;
                        if(s.isEmpty()){
                            result[curIndex][0] = -1;
                            s.add(i);
                            break;
                        }else{
                            result[curIndex][0] = s.peek();
                        }
                    }else{
                        s.add(i);
                        break;
                    }
                }
            }
        }
        while(!s.isEmpty()){
            int curIndex = s.pop();
            result[curIndex][1] = -1;
            if(s.isEmpty()){
                result[curIndex][0] = -1;
            }else{
                result[curIndex][0] = s.peek();
            }
        }
        
        return result;
    }

}
